package com.kobeliu.entity;

/**
 * 剑指  50
 *
 * 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
 *
 * 示例 1:
 * 输入：s = "abaccdeff"
 * 输出：'b'
 *
 * 示例 2:
 * 输入：s = ""
 * 输出：' '
 */

import java.util.*;

public class Demo_38_sword_50 {

    public static void main(String[] args) {


    }

    /**
     * 效率太低，需要改进，使用动态规划做的
     * @param s
     * @return
     */
    public static char firstUniqChar(String s) {

        Map<Integer, List<Character>> m = new HashMap<>();
        List<Character> chars = new ArrayList<>();
        Set<Character> set = new HashSet<>();
        int len = s.length(); //长度
        if(len== 0) return ' ';
        int i = 1; //指针
        Character c;
        chars.add(s.charAt(0));
        m.put(0,chars);
        set.add(s.charAt(0));

        while(i<len){
            c=s.charAt(i);
            List<Character> characters = m.get(i - 1);
            if(characters.contains(c)){
                characters.remove(c);
                if(!set.contains(c)){
                    set.add(c);
                }
            }else{
                if(!set.contains(c)){
                    characters.add(c);
                }
            }
            m.put(i,characters);
            i++;
        }

        chars = m.get(len-1);
        if(chars.size()>0) return chars.get(0);
        return ' ';

    }
}
